package recursion;

//迷宫问题
public class MiGong {
	public static void main(String[] args) {
		//创建一个二维数组，模拟迷宫
		//地图
		int[][] map = new int[8][7];
		//使用 1 表示墙
		//上下全部赋值 1
		for (int i = 0; i < 7; i++) {
			map[0][i] = 1;
			map[7][i] = 1;
		}
		//把左右赋值 1
		for (int i = 0; i < 8; i++) {
			map[i][0] = 1;
			map[i][6] = 1;
		}

		//设置地形挡板
		map[3][1] = 1;
		map[3][2] = 1;

		map[6][4] = 1;
		map[5][4] = 1;
		//输出地图
		System.out.println("地图");
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

		//使用递归回溯，给小球找路
		setWay(map, 1, 1);

		//输出走过的地图
		System.out.println("走过的地图");
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	//使用递归，来给小球找路
	//说明
	//当 map[i][j] = 0 表示没有走过
	//当 map[i][j] = 1 表示墙
	//当 map[i][j] = 2 表示走过
	//当 map[i][j] = 3 表示走过但走不通
	//走迷宫时，需要一个策略：下 -> 右 -> 上 -> 左，走不通再回溯

	/**
	 * @param map 表示地图
	 * @param i
	 * @param j   i，j为开始的坐标
	 * @return 能否找到去 （6，5） 的路径
	 */
	public static boolean setWay(int[][] map, int i, int j) {
		if (map[6][5] == 2) {
			//通路找到
			return true;
		} else {
			//先看该节点是否走过
			if (map[i][j] == 0) {//如果这个点没有走过
				map[i][j] = 2;//假定该点能走通
				if (setWay(map, i + 1, j)) {//先下走
					return true;
				} else if (setWay(map, i, j + 1)) {//向右走
					return true;
				} else if (setWay(map, i - 1, j)) {//向上走
					return true;
				} else if (setWay(map, i, j - 1)) {//向左走
					return true;
				} else {//走不通，则赋值为 3
					map[i][j] = 3;
					return false;
				}
			} else {//如果 map[i][j] 不为 0 ，则可能时 1 . 2 . 3,不需要走了
				return false;
			}
		}
	}
}
